package ReusableCode;

import java.math.*;
import java.util.*;

public class PrimeFunctions {

	public static boolean isPrime(long n) {
	    if(n < 2) return false;
	    if(n == 2 || n == 3) return true;
	    if(n%2 == 0 || n%3 == 0) return false;
	    long sqrtN = (long)Math.sqrt(n)+1;
	    for(long i = 6L; i <= sqrtN; i += 6) {
	        if(n%(i-1) == 0 || n%(i+1) == 0) return false;
	    }
	    return true;
	}
	
	public static HashSet<Integer> GetPrimesHash(int max)
	{
		HashSet<Integer> primes = new HashSet<Integer>();
		int limit = max;
		boolean[] sieve = new boolean[limit + 1];
		int limitSqrt = (int)Math.sqrt((double)limit);
		
		if(max < 2)
		{
			return new HashSet<Integer>();
		}
		else if(max<5)
		{
			HashSet<Integer> temp = new HashSet<Integer>();
			temp.add(2);
			temp.add(3);
			return temp;
		}
		
		Arrays.fill(sieve, false);

		sieve[0] = false;
		sieve[1] = false;
		sieve[2] = true;
		sieve[3] = true;

		for (int x = 1; x <= limitSqrt; x++) {
		    for (int y = 1; y <= limitSqrt; y++) {
		        // first quadratic using m = 12 and r in R1 = {r : 1, 5}
		        int n = (4 * x * x) + (y * y);
		        if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
		            sieve[n] = !sieve[n];
		        }
		        // second quadratic using m = 12 and r in R2 = {r : 7}
		        n = (3 * x * x) + (y * y);
		        if (n <= limit && (n % 12 == 7)) {
		        	sieve[n] = !sieve[n];
		        }
		        // third quadratic using m = 12 and r in R3 = {r : 11}
		        n = (3 * x * x) - (y * y);
		        if (x > y && n <= limit && (n % 12 == 11)) {
		            sieve[n] = !sieve[n];
		        }     
		    }
		} 
		
		// remove all perfect squares since the quadratic
		// wheel factorization filter removes only some of them
		for (int n = 5; n <= limitSqrt; n++) {
		    if (sieve[n]) {
		        int x = n * n;
		        for (int i = x; i <= limit; i += x) {
		            sieve[i] = false;
		        }
		    } 
		}
		
		// put the primes in a List.
		for (int i = 0; i <= limit; i++) {
			if (sieve[i]){
				primes.add(i);
		    }
		}
		
		return primes;
	}
	
	public static List<Integer> GetPrimes(int max)
	{
		List<Integer> primes = new ArrayList<Integer>();
		int limit = max;
		boolean[] sieve = new boolean[limit + 1];
		int limitSqrt = (int)Math.sqrt((double)limit);
		
		if(max < 2)
		{
			return new ArrayList<Integer>();
		}
		else if(max<5)
		{
			List<Integer> temp= new ArrayList<Integer>();
			temp.add(2);
			temp.add(3);
			return temp;
		}
		
		Arrays.fill(sieve, false);

		sieve[0] = false;
		sieve[1] = false;
		sieve[2] = true;
		sieve[3] = true;

		for (int x = 1; x <= limitSqrt; x++) {
		    for (int y = 1; y <= limitSqrt; y++) {
		        // first quadratic using m = 12 and r in R1 = {r : 1, 5}
		        int n = (4 * x * x) + (y * y);
		        if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
		            sieve[n] = !sieve[n];
		        }
		        // second quadratic using m = 12 and r in R2 = {r : 7}
		        n = (3 * x * x) + (y * y);
		        if (n <= limit && (n % 12 == 7)) {
		        	sieve[n] = !sieve[n];
		        }
		        // third quadratic using m = 12 and r in R3 = {r : 11}
		        n = (3 * x * x) - (y * y);
		        if (x > y && n <= limit && (n % 12 == 11)) {
		            sieve[n] = !sieve[n];
		        }     
		    }
		} 
		
		// remove all perfect squares since the quadratic
		// wheel factorization filter removes only some of them
		for (int n = 5; n <= limitSqrt; n++) {
		    if (sieve[n]) {
		        int x = n * n;
		        for (int i = x; i <= limit; i += x) {
		            sieve[i] = false;
		        }
		    } 
		}
		
		// put the primes in a List.
		for (int i = 0; i <= limit; i++) {
			if (sieve[i]){
				primes.add(i);
		    }
		}
		
		return primes;
	}
	
	//Check if the given numbers are consecutive primes.
	public static boolean consecutivePrimes(List<Long> primes)
	{
		long max=Long.MIN_VALUE, min=Long.MAX_VALUE;
		
		//Get the max and min values.
		for(int i = 0; i < primes.size(); i++)
		{
			if (!BigInteger.valueOf(primes.get(i)).isProbablePrime(15)){
				return false;
			}
			if(primes.get(i)>max)
			{
				max = primes.get(i);
			}
			
			if(primes.get(i)<min)
			{
				min = primes.get(i);
			}
		}
		
		//Check that the given primes are the only primes in the range.
		for(long i = min; i <= max; i++)
		{
			//if(isPrime(i))
			if(BigInteger.valueOf(i).isProbablePrime(15))
			{
				if(!primes.contains(i))
				{
					return false;
				}
			}
		}
		
		return true;
	}
	
	public static boolean isPrimeGenerating(long num) 
	{
		List<Long> divisors = MathFunctions.getDivisors(num);
		
		for(int j = 0; j < divisors.size(); j++)
		{
			long res = divisors.get(j) +  (num/divisors.get(j));
			
			if(!PrimeFunctions.isPrime(res))
			{
				return false;
			}
		}
	
		return true;
	}
	
	//Perform prime factorization on the given number.
	public static HashSet<Integer> factorizeHash(long num)
	{
		List<Integer> primes = PrimeFunctions.GetPrimes((int)Math.pow(2, 16));
		return factorizeHash(num, primes);
	}
	
	//Perform prime factorization on the given number.
	public static HashSet<Integer> factorizeHash(long num, List<Integer> primes)
	{
		HashSet<Integer> factors = new HashSet<Integer>();
		
		for(int i = 0; i < primes.size() && i <= num; i++)
		{
			long temp = num;
			int prime = primes.get(i);
			
			if(temp%prime==0)
			{
				factors.add(prime);
			}
		}
		
		return factors;
	}
	
	//Perform prime factorization on the given number.
	public static List<Integer> factorize(long num)
	{
		List<Integer> primes = PrimeFunctions.GetPrimes((int)Math.pow(2, 16));
		List<Integer> factors = new ArrayList<Integer>();
		
		for(int i = 0; i < primes.size(); i++)
		{
			long temp = num;
			int prime = primes.get(i);
			
			while(temp%prime==0)
			{
				factors.add(prime);
				temp /= prime;
			}
		}
		
		return factors;
	}	
}